package dp;

import java.util.Scanner;

/**
 * 只能往下或右，矩阵中每个格子数不一样，从左下角到右下角和最大的路径
 * 
 * @author Administrator
 * 
 */
public class MaxSumOfTwodimension {

	public static void main(String[] args) {

		// 输入m行n列的数组
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入矩阵的行列数，中间用空格隔开");
		int m = scanner.nextInt();
		int n = scanner.nextInt();
		// 避免无效输入
		if (m < 0 || n < 0) {
			System.err.println("您输入的数据有误，数组长度不能为负");
		} else {
			int[][] array = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					array[i][j] = scanner.nextInt();
				}
			}
			scanner.close();
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					System.out.print(array[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println("最大和" + maxSum(array, m, n));
		}
	}

	// 采用动态规划算法
	// sum[i][j]表示到第i行j列最大的和。
	// sum[i][j]=Array[i][j]+max(sum[i-1][j](if i>0),sum[i][j-1](if j>0));
	public static final int maxSum(int[][] array, int m, int n) {
		if (array == null || m <= 0 || n <= 0) {
			System.out.println("输入的数组为空");
			return 0;
		}
		int[][] sum = new int[m][n];
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				// 记录当前值
				int increment = array[i][j];
				int up = 0, left = 0;
				if (j > 0) {
					up = sum[i][j - 1];
				}
				if (i > 0) {
					left = sum[i - 1][j];
				}
				int neigbour = up > left ? up : left;  
				sum[i][j] = neigbour + increment;
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(sum[i][j] + " ");
			}
			System.out.println();
		}
		return sum[m - 1][n - 1];
	}
}
